# Definition for singly-linked list.
"""
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

层级遍历
堆排
"""
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        dimmyhead = ListNode(0)
        cur = dimmyhead
        while lists:
            index = 0
            min = float("inf")
            lists = list(filter(lambda x: x is not None,lists))
            if len(lists) == 0: break
            for i,x in enumerate(lists):
                if x and x.val <= min:
                    index = i
                    min = x.val
            cur.next = ListNode(min)
            cur = cur.next
            if lists[index]:
                lists[index] = lists[index].next
            else:
                lists.pop(index)
        return dimmyhead.next

    def mergeKLists1(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        List = []
        ret = []
        for t in lists:
            r = t
            while r != None:
                List.append(r.val)
                r = r.next
        for i in range(len(List) // 2, 0, -1):
            self.max_heap(List, i)
        while len(List) > 0:
            tmp = List[0]
            List[0] = List[-1]
            List[-1] = tmp
            ret.insert(0, List.pop())
            self.max_heap(List, 1)
        return ret

    def max_heap(self, List, i):
        l = i * 2
        r = l + 1
        z = i
        length = len(List)
        if l <= length and List[z - 1] < List[l - 1]:
            z = l
        if r <= length and List[z - 1] < List[r - 1]:
            z = r
        if z != i:
            tmp = List[z - 1]
            List[z - 1] = List[i - 1]
            List[i - 1] = tmp
            self.max_heap(List, z)